<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        //时间复杂度：O(nlogn)，递归劈成两半logn,循环n次，所以nlogn 空间复杂度:O(n) 
        //稳定性：归并排序是稳定的排序算法
        function mergeSort(arr) {
            if (arr.length < 2) {
                return arr;
            }
            const midIndex = Math.floor(arr.length / 2);
            const left = arr.slice(0, midIndex);
            const right = arr.slice(midIndex, arr.length);
            return merge(mergeSort(left), mergeSort(right));
        }

        function merge(left, right) {
            let temp = [];//空间+1
            while (left.length && right.length) {
                temp.push(left[0] < right[0] ? left.shift() : right.shift());
            }
            while (left.length) {
                temp.push(left.shift());
            }
            while (right.length) {
                temp.push(right.shift());
            }
            return temp;
        }

        const arr = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0];
        console.log(mergeSort(arr));

    </script>
</body>

</html>